Skip to main content

Asymptotic Notation

Asymptotic notation is a mathematical tool used in computer science to describe the efficiency of algorithms in terms of time and space complexity. It helps us analyze how the runtime or space requirements of an algorithm grow as the input size increases.

Asymptotic notation ignores constant factors and lower-order terms, focusing only on the dominant factor that affects performance for large inputs.

Types of Asymptotic Notations​

1. Big-O Notation (O) – Upper Bound (Worst Case)​

  • Represents the worst-case complexity.
  • Describes the maximum amount of time an algorithm will take for any input.
  • Example: If an algorithm runs in at most c · f(n) time for large n , we write T(n) = O(f(n))

2. Omega Notation (Ω) – Lower Bound (Best Case)​

  • Represents the best-case complexity.
  • Guarantees that the algorithm takes at least a certain amount of time.
  • Example: If an algorithm runs in at least c · f(n) time for large n, we write T(n) = Ω(g(n))

3. Theta Notation (Θ) – Tight Bound (Average Case)​

  • Represents both upper and lower bounds.
  • Used when an algorithm always runs in a specific range of time complexity.
  • Example: If an algorithm runs in both O(f(n)) and Ω(f(n)), we write: T(n) = Θ(f(n))
  • Polynomial - 1, log n, n log n
  • Exponential - 2n, 3n, nn

Adiitional Notes​

  • Always use call by reference for recursive call.
  • When declare integer vector set default value as -1.